package ai.zixing.mashibing.basic_class.class11;

/**
 * 规定1和A对应、2和B对应、3和C对应...
 * 那么一个数字字符串比如"111”就可以转化为:
 * "AAA"、"KA"和"AK"
 * 给定一个只有数字字符组成的字符串str，返回有多少种转化结果
 *
 * 【从左往右】
 */
public class Code06_ConvertToLetterString {

    public static int number(String str) {
        if (str == null || str.isEmpty()) {
            return 0;
        }
        return process(str.toCharArray(), 0);
    }

    // str[0...i]已经转化完
    // i 位置之前的不用管
    // i... 有多少中转化结果
    // i 本身转化，i 和 i+1 转化，两个字符才可能小于 26， 字符是 1-26
    public static int process(char[] str, int i) {
        // base case
        // 转换为本身
        if (i == str.length) {
            return 1;
        }
        // str[i] 是 '0' 字符不能转化，如 "075", "10"
        if (str[i] == '0') {
            return 0;
        }
        // i 没有到终止位置
        // str[i] 是 '1'
        if (str[i] == '1') {
            // i自己作为单独的部分，后续有多少种方法
            int res = process(str, i + 1);
            // (i和i+1)作为单独的部分，后续有多少种方法
            if (i + 1 < str.length) {
                res += process(str, i + 2);
            }
            return res;
        }
        // str[i] 是 '2'
        if (str[i] == '2') {
            // i自己作为单独的部分，后续有多少种方法
            int res = process(str, i + 1);
            // (i和i+1)作为单独的部分并且没有超过26，后续有多少种方法
            if (i + 1 < str.length && (str[i + 1] >= '0') && str[i + 1] <= '6') {
                res += process(str, i + 2);
            }
            return res;
        }
        // str[i] 大于 '2'，即 处于 '3'~'9' 则没有对应的字符，看下一个字符
        return process(str, i + 1);
    }

    public static int process2(char[] str, int i) {
        if (i == str.length) {
            return 1;
        }
        if (str[i] == '0') {
            return 0;
        }
        if (str[i] == '1') {
            int res = process(str, i + 1);
            if (i + 1 < str.length) {
                res += process(str, i + 2);
            }
            return res;
        }
        if (str[i] == '2') {
            int res = process(str, i + 1);
            if (i + 1 < str.length && (str[i + 1] >= '0') && str[i + 1] <= '6') {
                res += process(str, i + 2);
            }
            return res;
        }
        return process(str, i + 1);
    }

    public static int dpWays(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int[] dp = new int[N + 1];

        // dp生成规则 =====================
        // i == str.length
        dp[N] = 1;
        for (int i = N - 1; i >= 0 ; i--) {
            //pd[i]; process2 中 return 时，就是设置 pb[i]的时刻
            if (str[i] == '0') {
                dp[i] =  0;
            } else
            if (str[i] == '1') {
                dp[i] = dp[i + 1];
                if (i + 1 < N) {
                    dp[i] += dp[i + 2];
                }
            } else if (str[i] == '2') {
                dp[i] = dp[i + 1];
                if (i + 1 < N && (str[i + 1] >= '0') && str[i + 1] <= '6') {
                    dp[i] += dp[i + 2];
                }
            } else {
                dp[i] = dp[i + 1];
            }
        }
        return dp[0];
    }

    public static void main(String[] args) {
        System.out.println(number("11111"));
        System.out.println(dpWays("11111"));

    }
}
